// https://www.lintcode.com/problem/sort-colors-ii/

public class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        // write your code here
        // 原来有个算法叫彩虹排序...
        rainbowSort(colors, 0, colors.length - 1, 1, k);
    }

    protected void rainbowSort(int[] colors, int left, int right, int kFrom, int kTo) {
        if ((kFrom != kTo) && (left < right)) {
            int kMid = (kFrom + kTo) / 2;
            int l = left;
            int r = right;
            while (l <= r) {
                while ((l <= r) && (colors[l] <= kMid)) {
                    ++l;
                }
                while ((l <= r) && (colors[r] > kMid)) {
                    --r;
                }
                if (l <= r) {
                    int t = colors[l];
                    colors[l] = colors[r];
                    colors[r] = t;
                    ++l;
                    --r;
                }
            }
            rainbowSort(colors, left, r, kFrom, kMid);
            rainbowSort(colors, l, right, kMid + 1, kTo);
        }
    }
}